# Copyright 2010 G. M. Bond. All Rights Reserved.
# Licensed to PSF under a Contributor Agreement.

"""
State machine based node matcher.
"""

EPSILON = 0 #Empty transition
TYPE = 1    #Transition based on type
STRING = 2  #Transition based on string matching
ANY = 3     #Transition matches any node
CLOSE = 4   #Transition matches end of specific node

#TODO Matt: Handle registration of starting a possible match

class Pattern_Matcher(object):
    """
    Holds the overall state and handles transitions.
    
    Currently inefficient, based on function calls. Could be compiled
    into a more efficient structure once generation is complete.
    """

    def __init__(self, priority=1):
        """Set up the initial states"""
        self.states = set()
        self.new_states = set()
        self.accept_states = set()
        self.start_state = None
        self.priority = priority

    def register_accept(self, state):
        """Add state to the set of accepting states"""
        self.accept_states.add(state)
    
    def next_node(self, node):
        """
        Determine the next set of states based on current states and
        input node
        """
        self.new_states.clear()
        transitions = (x.move(node) for x in self.states)
        if len(transitions) < 1:
            #No possible nodes returned. This means the input is not valid for
            #this pattern and we should return to the start
            #We could also find a way to skip accept testing if this branch
            #executes, as it might speed things up.
            transitions.add(self.pattern_start)
        transitions.update(n.e_closure for n in transitions)
        self.new_states.update(transitions)

    def check_for_accept(self):
        """
        Checks if we have entered any accepting states.
        Returns accepting states as a list sorted by priority.
        This might be improved by returning only the highest priority
        matching state instead of sorting the whole list.
        """
        s = None
        accepts = intersection(self.new_states, self.accept_states)
        if len(accepts) > 0:
            s = sorted(accepts, key=lambda state: state.priority)
        return s

class State(object):
    """An individual state and associated transitions"""

    def __init__(self, matcher):
        """
        Setup the state. Matcher should be a reference to the containing
        Pattern_Matcher, and first should be a reference to the first state in
        the pattern, used for transitioning to the beginning of the pattern
        when nothing else matches during a transition
        """
        self.transitions = set()
        self.matcher = matcher

    def accept(self, action):
        """Set node to accept state and save action function"""
        self.accept = TRUE
        self.matcher.register_accept(self)
        self.action = action

    def add_transition(self, type, node, condition=None):
        """Register a transition out of this node"""
        #This is all just sanity checking and could be dropped for speed
        if type == EPSILON:
            assert condition is None
        elif type == TYPE:
            assert condition # is a valid node type? Where do we get that?
        elif type == STRING:
            #convert to unicode just in case
            condition = unicode(condition)
        elif type == ANY:
            assert condition is None
        elif type == CLOSE:
            #We're looking for an id here, but we don't know it at compile time
            #So we should pass it another node. When this is tested, we'll look
            #at the id of the node that matched in the node we were passed
            assert condition # isint?
        self.transitions.add( (type, node, condition) )

    @property
    def e_closure(self):
        """Get the epsilon closure of the node."""
        try:
            return self._e_closure
        except NameError:
            f = lambda n : n[1] if n[0] == EPSILON else None
            nodes = (f(n) for n in self.transitions)
            nodes.update(n.e_closure for n in nodes)
            nodes.add(self)
            self._e_closure = nodes
            return self._e_closure

    def move(self, in_node):
        """
        Get the node(s) active after following all possible transitions
        based on in_node, except those reached through epsilon transitions
        """
        nodes = set()
        for t in self.transitions:
            if t[0] == EPSILON:
                continue
            if t[1] in nodes:
                #it might save a costly comparison, especially in regard to 
                #string comparison? Maybe?
                continue
            else:
                if t[0] == ANY or \
                   (t[0] == TYPE and t[2] == in_node.type) or \
                   (t[0] == CLOSE and t[2] == id(node)) or \
                   (t[0] == STRING and t[2] == node.value):
                    nodes.add(t[1])

        return nodes
